/*
 * Tester.c
 *
 *  Created on: 19/mag/2013
 *      Author: Ialenti Andrea, Marangon Fabio
 */

#include "../headers/BranchAndBound.h"
#include "../headers/Callback.h"
#include "../headers/CPLEXProblemGenerator.h"
#include "../headers/CPLEXProblemSolver.h"
#include "../headers/CPLEXUtility.h"
#include "../headers/Graph.h"
#include "../headers/Heuristic.h"
#include "../headers/Lagrangian.h"
#include "../headers/OneTree.h"
#include "../headers/Printer.h"
#include "../headers/StatusCodes.h"
#include "../headers/Tester.h"
#include "../headers/Utility.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include <ilcplex/cplex.h>

void parseCommandLine(const Config *cfg, int argc, char **argv, bool *verbosity, char *fileName, bool *nodePerm, bool *use3Opt, bool *useProxSrch, bool *useCPLEX, bool *useCB) {
	char *funcName = initCharArray(cfg->NAME_LEN);
	sprintf(funcName, "parseCommandLine");

	fprintf(stdout, "\t'%s': parsing command line parameters. . .\n", funcName);
	time_t t1, t2;
	time(&t1);
	switch(argc) {
		case 2: {
			*verbosity = (atoi(argv[1]) == 0) ? false : true;
			strcpy(fileName, cfg->DFLT_PROB);
			*nodePerm = cfg->DFLT_NODE_PERM;
			*use3Opt = cfg->DFLT_USE_3OPT;
			*useProxSrch = cfg->DFLT_USE_PS;
			*useCPLEX = cfg->DFLT_USE_CPLEX;
			*useCB = cfg->DFLT_USE_CB;
			break;
		}
		case 3: {
			*verbosity = (atoi(argv[1]) == 0) ? false : true;
			strcpy(fileName, argv[2]);
			*nodePerm = cfg->DFLT_NODE_PERM;
			*use3Opt = cfg->DFLT_USE_3OPT;
			*useProxSrch = cfg->DFLT_USE_PS;
			*useCPLEX = cfg->DFLT_USE_CPLEX;
			*useCB = cfg->DFLT_USE_CB;
			break;
		}
		case 4: {
			*verbosity = (atoi(argv[1]) == 0) ? false : true;
			strcpy(fileName, argv[2]);
			*nodePerm = (atoi(argv[3]) == 0) ? false : true;
			*use3Opt = cfg->DFLT_USE_3OPT;
			*useProxSrch = cfg->DFLT_USE_PS;
			*useCPLEX = cfg->DFLT_USE_CPLEX;
			*useCB = cfg->DFLT_USE_CB;
			break;
		}
		case 5: {
			*verbosity = (atoi(argv[1]) == 0) ? false : true;
			strcpy(fileName, argv[2]);
			*nodePerm = (atoi(argv[3]) == 0) ? false : true;
			*use3Opt = (atoi(argv[4]) == 0) ? false : true;
			*useProxSrch = cfg->DFLT_USE_PS;
			*useCPLEX = cfg->DFLT_USE_CPLEX;
			*useCB = cfg->DFLT_USE_CB;
			break;
		}
		case 6: {
			*verbosity = (atoi(argv[1]) == 0) ? false : true;
			strcpy(fileName, argv[2]);
			*nodePerm = (atoi(argv[3]) == 0) ? false : true;
			*use3Opt = (atoi(argv[4]) == 0) ? false : true;
			*useProxSrch = (atoi(argv[5]) == 0) ? false : true;
			*useCPLEX = cfg->DFLT_USE_CPLEX;
			*useCB = cfg->DFLT_USE_CB;
			break;
		}
		case 7: {
			*verbosity = (atoi(argv[1]) == 0) ? false : true;
			strcpy(fileName, argv[2]);
			*nodePerm = (atoi(argv[3]) == 0) ? false : true;
			*use3Opt = (atoi(argv[4]) == 0) ? false : true;
			*useProxSrch = (atoi(argv[5]) == 0) ? false : true;
			*useCPLEX = (atoi(argv[6]) == 0) ? false : true;
			*useCB = cfg->DFLT_USE_CB;
			break;
		}
		case 8: {
			*verbosity = (atoi(argv[1]) == 0) ? false : true;
			strcpy(fileName, argv[2]);
			*nodePerm = (atoi(argv[3]) == 0) ? false : true;
			*use3Opt = (atoi(argv[4]) == 0) ? false : true;
			*useProxSrch = (atoi(argv[5]) == 0) ? false : true;
			*useCPLEX = (atoi(argv[6]) == 0) ? false : true;
			*useCB = (atoi(argv[7]) == 0) ? false : true;
			break;
		}
		default: {
			fprintf(stdout, "\t'%s': using default parameters. . .\n", funcName);
			*verbosity = cfg->DFLT_VERBOSITY;
			strcpy(fileName, cfg->DFLT_PROB);
			*nodePerm = cfg->DFLT_NODE_PERM;
			*use3Opt = cfg->DFLT_USE_3OPT;
			*useProxSrch = cfg->DFLT_USE_PS;
			*useCPLEX = cfg->DFLT_USE_CPLEX;
			*useCB = cfg->DFLT_USE_CB;
			break;
		}
	}
	time(&t2);

	//	Print the chosen parameters.
	if (*verbosity) {
		fprintf(stdout, "\t\tVerbosity: enabled\n");
		fprintf(stdout, "\t\tInput file: '%s'\n", fileName);

		if(*useProxSrch) {
			fprintf(stdout, "\t\tSolving mode: proximity search + CPLEX with callbacks\n");
			fprintf(stdout, "\t\tProximity search time limit: %0.2f - %0.2f - %0.2f - %0.2f hour(s) (normalized time), depending on problem size\n", (double)cfg->CPX_PS_GTL / 3600, (double)cfg->CPX_PS_GTL / 3600 * 2, (double)cfg->CPX_PS_GTL / 3600 * 4, (double)cfg->CPX_PS_GTL / 3600 * 6);
			fprintf(stdout, "\t\tCPLEX time limit: %0.2f hour(s) (normalized time)\n", (double)cfg->CPX_TIME_LIM / 3600);
			fprintf(stdout, "\t\tCPLEX memory limit: %0.0f GB, writing compressed node-files to disk\n", (double)cfg->CPX_MEM_LIM / 1024);
		}
		else {
			if (*useCPLEX) {
				if (*useCB)
					fprintf(stdout, "\t\tSolving mode: CPLEX with callbacks\n");
				else
					fprintf(stdout, "\t\tSolving mode: CPLEX without callbacks (Miliotis' method)\n");
				fprintf(stdout, "\t\tCPLEX time limit: %0.2f hour(s) (normalized time)\n", (double)cfg->CPX_TIME_LIM / 3600);
				fprintf(stdout, "\t\tCPLEX memory limit: %0.0f GB, writing compressed node-files to disk\n", (double)cfg->CPX_MEM_LIM / 1024);
			}
			else
				fprintf(stdout, "\t\tSolving mode: branch and bound\n");
		}
		fprintf(stdout, "\t\tNumber of threads (CPLEX only): %d\n", cfg->CPX_TH_CNT);
		if(*nodePerm)
			fprintf(stdout, "\t\tGraph nodes permutation: enabled\n");
		else
			fprintf(stdout, "\t\tGraph nodes permutation: disabled\n");
		if(*use3Opt)
			fprintf(stdout, "\t\t3-Opt: %d moves enabled for each nearest neighbor run\n", cfg->IT_3OPT);
		else
			fprintf(stdout, "\t\t3-Opt: disabled\n");
		fprintf(stdout, "\t'%s': command line arguments parsed in %0.2f second(s). . .\n", funcName, difftime(t2, t1));
	}
	else
		fprintf(stdout, "\t\tVerbosity: disabled\n");

	freeCharArray(funcName);
	return;
}

Status importProblem(const Config *cfg, char *fileName, Graph *g, bool verbose, bool nodePerm) {
	char *funcName = initCharArray(cfg->NAME_LEN);
	sprintf(funcName, "importProblem");

	time_t t1, t2;
	double execTime, normTime;

	//	Generate random graph.
	if (strcmp(fileName, "r") == 0 || strcmp(fileName, "R") == 0) {

		if (verbose)
			fprintf(stdout, "\n\t'%s': generating random graph. . .", funcName);

		//TODO generate random graph.
		if (verbose) {
			fprintf(stdout, "\n***'%s': random graph generation currently not implemented. . .\n\n", funcName);
			return ERR_MAIN;
		}
		//ask the number of nodes and the seed then proceed.
	}
	//	Import the TSP-lib problem.
	else {
		if (verbose)
			fprintf(stdout, "\t'%s': importing graph data from TSP-LIB file '%s'. . .\n", funcName, fileName);
		time(&t1);

		//	Try to import the graph data.
		Status status = importGraph(cfg, fileName, g, nodePerm, verbose);
		if (status != SUCCESS) {
			fprintf(stdout, "***'%s': could not import graph from file '%s', defaulting to file '%s'. . .\n", funcName, fileName, cfg->DFLT_PROB);
			status = importGraph(cfg, cfg->DFLT_PROB, g, nodePerm, verbose);
			if (status != SUCCESS) {
				fprintf(stdout, "***'%s': could not import graph from default file '%s'. Status %d. . .\n", funcName, cfg->DFLT_PROB, getStatusCode(status));
				disposeGraph(g);
				freeCharArray(funcName);
				return ERR_IMPORT_GRAPH;
			}
		}
		time(&t2);
		if (verbose) {
			execTime = difftime(t2, t1);
			normTime = execTime * cfg->NORM_TIME;
			fprintf(stdout, "\t'%s': graph import completed in %0.2f second(s) (%0.2f second(s) normalized time). . .\n", funcName, execTime, normTime);
		}
	}
	freeCharArray(funcName);
	return SUCCESS;
}

Status simplifyProblem(const Config *cfg, Graph *g, double *LB, double *UB, OneTree *lagrTree, OneTree *heuTour, bool use3Opt, bool *lagrOpt, bool verbose) {
	char *funcName = initCharArray(cfg->NAME_LEN);
	sprintf(funcName, "simplifyProblem");

	Status status;
	time_t t1, t2;
	double execTime, normTime;
	char *fileName = initCharArray(cfg->NAME_LEN);
	if (fileName == NULL) {
		fprintf(stdout, "***'%s': memory allocation error. . .\n", funcName);
		return ERR_MEM_ALLOC;
	}

	//	Initialize the Lagrangian and the heuristic tour 1-trees.
	if (!initOneTree(cfg, lagrTree, g->size)) {
		fprintf(stdout, "***'%s': memory error during 1-tree initialization. . .\n", funcName);
		freeCharArray(funcName);
		freeCharArray(fileName);
		return ERR_MEM_ALLOC;
	}
	if (!initOneTree(cfg, heuTour, g->size)) {
		fprintf(stdout, "***'%s': memory error during 1-tree initialization. . .\n", funcName);
		freeCharArray(funcName);
		freeCharArray(fileName);
		disposeOneTree(lagrTree);
		return ERR_MEM_ALLOC;
	}

	//	Declare and initialize 1-trees and function 'L(u)'.
	OneTree tour;
	funcLu f;
	if (!initOneTree(cfg, &tour, g->size)) {
		fprintf(stdout, "***'%s': memory error during 1-tree initialization. . .\n", funcName);
		freeCharArray(funcName);
		freeCharArray(fileName);
		disposeOneTree(lagrTree);
		disposeOneTree(heuTour);
		return ERR_MEM_ALLOC;
	}
	if (!initFuncLu(cfg, &f, cfg->MAX_IT, cfg->STEP)) {
		fprintf(stdout, "***'%s': memory error during lagrangian function initialization. . .\n", funcName);
		freeCharArray(funcName);
		freeCharArray(fileName);
		disposeOneTree(lagrTree);
		disposeOneTree(heuTour);
		disposeOneTree(&tour);
		return ERR_MEM_ALLOC;
	}

	//	Run lagrangian relaxation and apply lagrangian coefficients to the original graph.
	if (verbose)
		fprintf(stdout, "\t'%s': performing the lagrangian relaxation. . .\n", funcName);
	time(&t1);
	status = computeLagrRlx(cfg, g, &f, verbose);
	if (status != SUCCESS) {
		fprintf(stdout, "***'%s': error (%d) computing the lagrangian relaxation. . .\n", funcName, getStatusCode(status));
		freeCharArray(funcName);
		freeCharArray(fileName);
		disposeOneTree(lagrTree);
		disposeOneTree(heuTour);
		disposeOneTree(&tour);
		disposeFuncLu(&f);
		return ERR_SIMPL_PROB;
	}

	*LB = f.best;
	time(&t2);
	if (verbose) {
		execTime = difftime(t2, t1);
		normTime = execTime * cfg->NORM_TIME;
		fprintf(stdout, "\t'%s': relaxation completed in %0.2f second(s) (%0.2f second(s) normalized time) after %d iteration(s)! Found lower bound = %0.2f. . .\n\n", funcName, execTime, normTime, f.size, f.best);
		sprintf(fileName, "%sfunc.dat", cfg->PLT_PATH);

		status = plotFunction(cfg, &f, fileName);
		if (status != SUCCESS) {
			fprintf(stdout, "***'%s': error (%d) plotting the lagrangian function 'L(u)'. . .\n", funcName, getStatusCode(status));
			freeCharArray(funcName);
			freeCharArray(fileName);
			disposeOneTree(lagrTree);
			disposeOneTree(heuTour);
			disposeOneTree(&tour);
			disposeFuncLu(&f);
			return ERR_PLOT;
		}
	}

	//	Compute and store the lagrangian 1-tree.
	computeOneTree(cfg, g, lagrTree);

	//	If the lagrangian relaxation finds the optimal tour, plot the solution and stop the program.
	if (f.size < cfg->MAX_IT) {
		fprintf(stdout, "\t'%s': lagrangian relaxation found the optimal tour cost: %0.0f. . .\n", funcName, f.best);

		//	Plot the solution.
		char *title = initCharArray(cfg->NAME_LEN);
		sprintf(title, "TSP optimal solution for '%s' found using the lagrangian relaxation. Optimal tour cost: %0.0f", g->name, lagrTree->totalCost);
		sprintf(fileName, "%stspOptLagr.dat", cfg->PLT_PATH);
		status = plotTour(cfg, lagrTree, fileName, title, cfg->COLOR_GREEN);
		if (status != SUCCESS) {
			fprintf(stdout, "***'%s': error (%d) plotting the optimal tour found using the lagrangian relaxation. . .\n", funcName, getStatusCode(status));
			freeCharArray(funcName);
			freeCharArray(fileName);
			disposeOneTree(lagrTree);
			disposeOneTree(heuTour);
			disposeOneTree(&tour);
			disposeFuncLu(&f);
			freeCharArray(title);
			return ERR_PLOT;
		}
		freeCharArray(title);
		*UB = lagrTree->totalCost;
		*lagrOpt = true;
	}

	//	Calculate the UB using the heuristic algorithms (on the lagrangian graph).
	if (verbose)
		fprintf(stdout, "\t'%s': running heuristic algorithm (nearest neighbor) O(n³) to find a starting upper bound. . .\n", funcName);
	time(&t1);
	int swaps = 0;
	status = findBestNN_2Opt_3Opt(cfg, g, &tour, &swaps, use3Opt, verbose);
	if (status != SUCCESS) {
		fprintf(stdout, "***'%s': error (%d) searching for the heuristic tour. . .\n", funcName, getStatusCode(status));
		freeCharArray(funcName);
		freeCharArray(fileName);
		disposeOneTree(lagrTree);
		disposeOneTree(heuTour);
		disposeOneTree(&tour);
		disposeFuncLu(&f);
		return ERR_SIMPL_PROB;
	}
	*UB = tour.totalCost;
	time(&t2);
	if (verbose) {
		execTime = difftime(t2, t1);
		normTime = execTime * cfg->NORM_TIME;
		fprintf(stdout, "\n\t'%s': UB = %f (on the complete lagrangian graph), it was calculated in %0.2f second(s) (%0.2f second(s) normalized time). Total number of 2-opt swaps = %d!\n\n", funcName, *UB, execTime, normTime, swaps);
		char *title = initCharArray(cfg->NAME_LEN);
		sprintf(title, "Heuristic tour for '%s'. Tour cost: %0.0f", tour.name, tour.totalCost);
		sprintf(fileName, "%sheuTour.dat", cfg->PLT_PATH);
		status = plotTour(cfg, &tour, fileName, title, cfg->COLOR_BLUE);
		if (status != SUCCESS) {
			fprintf(stdout, "***'%s': error (%d) plotting the heuristic tour. . .\n", funcName, getStatusCode(status));
			freeCharArray(funcName);
			freeCharArray(fileName);
			disposeOneTree(lagrTree);
			disposeOneTree(heuTour);
			disposeOneTree(&tour);
			disposeFuncLu(&f);
			freeCharArray(title);
			return ERR_PLOT;
		}
		freeCharArray(title);
	}

	//	Remove some graph edges.
	if (verbose)
		fprintf(stdout, "\t'%s': removing graph edges in O(n³) using LB = %0.2f, UB = %0.2f. . .\n", funcName, *LB, *UB);
	int origEdges = g->size * (g->size - 1) / 2;
	time(&t1);
	status = rmGraphEdges(cfg, g, *LB, *UB);
	if (status != SUCCESS) {
		fprintf(stdout, "***'%s': error (%d) removing graph edges. . .\n", funcName, getStatusCode(status));
		freeCharArray(funcName);
		freeCharArray(fileName);
		disposeOneTree(lagrTree);
		disposeOneTree(heuTour);
		disposeOneTree(&tour);
		disposeFuncLu(&f);
		return ERR_RM_EDGES;
	}
	time(&t2);
	if (verbose) {
		execTime = difftime(t2, t1);
		normTime = execTime * cfg->NORM_TIME;
		fprintf(stdout, "\t'%s': the graph was cleared in %0.2f second(s) (%0.2f second(s) normalized time). . .\n", funcName, execTime, normTime);
		fprintf(stdout,	"\t'%s': %d edges were removed (%0.2f %%), %d edges remaining (%0.2f %%). . .\n\n", funcName, origEdges - g->edgeCnt,	100 * (origEdges - g->edgeCnt) / (double) origEdges, g->edgeCnt, 100 * g->edgeCnt / (double) origEdges);
		sprintf(fileName, "%sprunedGraph.dat", cfg->PLT_PATH);
		status = plotGraph(cfg, g, fileName);
		if (status != SUCCESS) {
			fprintf(stdout, "***'%s': error (%d) plotting the pruned graph. . .\n", funcName, getStatusCode(status));
			freeCharArray(funcName);
			freeCharArray(fileName);
			disposeOneTree(lagrTree);
			disposeOneTree(heuTour);
			disposeOneTree(&tour);
			disposeFuncLu(&f);
			return ERR_PLOT;
		}
	}

	//	Save the heuristic tour.
	cpTree(&tour, heuTour);

	//	Free the memory.
	freeCharArray(funcName);
	freeCharArray(fileName);
	disposeOneTree(&tour);
	disposeFuncLu(&f);

	//	Restore the original graph costs for the CPLEX.
	restoreOrigCosts(g);
	return SUCCESS;
}

Status createProxySearchProblem(const Config *cfg, CPXENVptr *env, CPXLPptr *psLP, CPXLPptr *lp, Problem *p, Problem *psP, Graph *g, double LB, double UB, OneTree *tour, bool verbose) {
	char *funcName = initCharArray(cfg->NAME_LEN);
	sprintf(funcName, "createProxySearchProblem");

	//	Initialize 'Problem' data structures.
	if (!initProblem(cfg, p, g->size, g->edgeCnt)) {
		fprintf(stdout, "***'%s': error while initializing memory for the 'Problem' data structure. . .\n", funcName);
		freeCharArray(funcName);
		return ERR_MEM_ALLOC;
	}
	if (!initProblem(cfg, psP, g->size, g->edgeCnt)) {
		fprintf(stdout, "***'%s': error while initializing memory for the 'Problem' data structure. . .\n", funcName);
		freeCharArray(funcName);
		return ERR_MEM_ALLOC;
	}

	//	Create correspondences between the 'Graph' and the 'Problem'.
	Status status = createCorrespondences(cfg, p, g, verbose);
	status = createCorrespondences(cfg, psP, g, verbose);

	//	Generate the CPLEX proximity search problem.
	status = generateProxyProb(cfg, env, lp, psLP, p, psP, g, LB, UB, tour, verbose);
	if (status != SUCCESS) {
		fprintf(stdout, "***'%s': there was an error (%d) creating the CPLEX problem! Program terminated. . .\n", funcName, getStatusCode(status));
		freeCharArray(funcName);
		return status;
	}
	freeCharArray(funcName);
	return SUCCESS;
}

Status createCPLEXProblem(const Config *cfg, CPXENVptr *env, CPXLPptr *lp, Problem *p, Graph *g, double LB, double UB, bool verbose, bool useCB) {
	char *funcName = initCharArray(cfg->NAME_LEN);
	sprintf(funcName, "createCPLEXProblem");

	if (!initProblem(cfg, p, g->size, g->edgeCnt)) {
		fprintf(stdout, "***'%s': error while initializing memory for the 'Problem' data structure. . .\n", funcName);
		freeCharArray(funcName);
		return ERR_MEM_ALLOC;
	}

	//	Create correspondences between the 'Graph' and the 'Problem'.
	Status status = createCorrespondences(cfg, p, g, verbose);

	//	Generate the CPLEX problem
	status = generateProb(cfg, env, lp, p, g, LB, UB, useCB, verbose);
	if (status != SUCCESS) {
		fprintf(stdout, "***'%s': there was an error (%d) creating the CPLEX problem! Program terminated.\n", funcName, getStatusCode(status));
		freeCharArray(funcName);
		return status;
	}
	freeCharArray(funcName);
	return SUCCESS;
}

Status solveTSP_CB(const Config *cfg, CPXENVptr *env, CPXLPptr *lp, Problem *p, Graph *g, cbData *data, bool verbose) {
	char *funcName = initCharArray(cfg->NAME_LEN);
	sprintf(funcName, "solveTSP_CB");

	//	Initialize callbacks data.
	initCBData(cfg, data, g, p, lp, verbose);

	//	Set the two callbacks.
	fprintf(stdout, "\n\t'%s': setting the two callbacks to use 'cbLazySEC' and 'cbMinCut'. . .\n", funcName);
	int cpxStat = CPXsetlazyconstraintcallbackfunc(*env, cbLazySEC, data);
	if (cpxStat != CPX_SUCCESS) {
		fprintf(stdout, "***'%s': error (%d) setting the lazy constraint callback, program will terminate. . .\n", funcName, cpxStat);
		freeCharArray(funcName);
		return ERR_CPX;
	}
	cpxStat = CPXsetusercutcallbackfunc(*env, cbMinCut, data);
	if (cpxStat != CPX_SUCCESS) {
		fprintf(stdout, "***'%s': error (%d) setting the min cut callback, program will terminate. . .\n", funcName, cpxStat);
		freeCharArray(funcName);
		return ERR_CPX;
	}

	if (verbose)
		fprintf(stdout, "\t'%s': running MIP opt adding SECs using callbacks. . .\n\n\n", funcName);

	//	Optimize the problem.
	cpxStat = CPXmipopt(*env, *lp);
	if (cpxStat != CPX_SUCCESS) {
		fprintf(stdout, "***'%s': failed to optimize MIP. Status: %d. . .\n", funcName, cpxStat);
		freeCharArray(funcName);
		return ERR_CPX;
	}

	//	Check the CPLEX mip opt status.
	bool opt = true;
	cpxStat = CPXgetstat(*env, *lp);
	char code[CPXMESSAGEBUFSIZE];
	CPXgetstatstring(*env, cpxStat, code);
	fprintf(stdout, "\n\t'%s': optimization completed with status %d ('%s'). . .\n", funcName, cpxStat, code);
	if (cpxStat != CPXMIP_OPTIMAL && cpxStat != CPXMIP_OPTIMAL_TOL) {
		opt = false;
		if (verbose)
			fprintf(stdout, "\n\t'%s': *WARNING* MIP opt was stopped before it could certify the tour's optimality. CPLEX status: %d. . .\n\n", funcName, cpxStat);
	}

	//	Retrieve the optimal solution.
	double solution = 0;
	cpxStat = CPXgetobjval(*env, *lp, &solution);
	if (cpxStat != CPX_SUCCESS) {
		fprintf(stdout, "***'%s': no MIP objective value available. Status: %d, program terminating. . .\n", funcName, cpxStat);
		freeCharArray(funcName);
		return ERR_CPX;
	}

	//	Plot the CPLEX solution (using callbacks).
	Status status = plotSolution(cfg, *env, *lp, p, g, -2, false, opt);
	if (status != SUCCESS) {
		fprintf(stdout, "***'%s': error printing the solution. Error status: %d.\n", funcName, status);
		freeCharArray(funcName);
		return ERR_PLOT;
	}
	freeCharArray(funcName);
	return SUCCESS;
}

Status solveUsingMiliotis(const Config *cfg, CPXENVptr *env, CPXLPptr *lp, Problem *p, Graph *g, bool verbose) {
	char *funcName = initCharArray(cfg->NAME_LEN);
	sprintf(funcName, "solveUsingMiliotis");

	Status status;
	double solution = 0;
	int cpxStat;
	time_t t, t2;
	time(&t);

	if (verbose)
		fprintf(stdout, "\n\t'%s': problem created, running optimization function (MIP opt) for the first time. . .\n\n", funcName);

	//	Optimize the current problem.
	cpxStat = CPXmipopt(*env, *lp);
	if (cpxStat != CPX_SUCCESS) {
		fprintf(stdout, "***'%s': failed to optimize MIP. Status: %d. . .\n", funcName, cpxStat);
		freeCharArray(funcName);
		return ERR_CPX;
	}

	//	Retrieve the current solution.
	cpxStat = CPXgetobjval(*env, *lp, &solution);
	if (cpxStat != CPX_SUCCESS) {
		fprintf(stdout, "***'%s': no MIP objective value available. Status: %d. . .\n", funcName, cpxStat);
		freeCharArray(funcName);
		return ERR_CPX;
	}

	//	Plot the CPLEX solution (using callbacks).
	if (verbose) {
		status = plotSolution(cfg, *env, *lp, p, g, -1, false, false);
		if (status != SUCCESS) {
			fprintf(stdout, "***'%s': error printing the solution. Error status: %d. . .\n", funcName, status);
			freeCharArray(funcName);
			return ERR_PLOT;
		}
		fprintf(stdout, "\n\t'%s': MIP opt terminated. . .\n", funcName);
		fprintf(stdout, "\n\t'%s': searching TSP solution iteratively (Miliotis' method). . .\n\n", funcName);
	}

	//	Solve the problem iteratively.
	status = solveIterMiliotis(cfg, *env, *lp, p, g, verbose, false, t);
	if (status != SUCCESS) {
		if (status == ERR_TIME) {
			if (verbose) {
				time(&t2);
				fprintf(stdout, "\n\t'%s': global time limit reached. . . \n", funcName);
				fprintf(stdout, "\t\t'%s': elapsed time: %0.2f second(s) (%0.2f normalized time second(s)). . .\n", funcName, difftime(t2, t), difftime(t2, t) * cfg->NORM_TIME);
			}
		}
		else {
			fprintf(stdout, "***'%s': error (%d) solving the problem iteratively. . .\n", funcName, getStatusCode(status));
			freeCharArray(funcName);
			return ERR_TESTER;
		}
	}

	//	Check the CPLEX mip opt status.
	bool opt = true;
	cpxStat = CPXgetstat(*env, *lp);
	char code[CPXMESSAGEBUFSIZE];
	CPXgetstatstring(*env, cpxStat, code);
	fprintf(stdout, "\n\t'%s': optimization completed with status %d ('%s'). . .\n", funcName, cpxStat, code);
	if (cpxStat != CPXMIP_OPTIMAL && cpxStat != CPXMIP_OPTIMAL_TOL) {
		opt = false;
		if (verbose)
			fprintf(stdout, "\n\t'%s': *WARNING* MIP opt was stopped before it could certify the tour's optimality. CPLEX status: %d. . .\n\n", funcName, cpxStat);
	}

	//	Get the final TSP solution.
	solution = 0;
	cpxStat = CPXgetobjval(*env, *lp, &solution);
	if (cpxStat != CPX_SUCCESS) {
		fprintf(stdout, "***'%s': no MIP objective value available. Status: %d. . .\n", funcName, cpxStat);
		freeCharArray(funcName);
		return ERR_CPX;
	}

	//	Plot the TSP solution.
	fprintf(stdout, "\t'%s': CPLEX TSP optimal solution: %0.2f. . .\n", funcName, solution);
	status = plotSolution(cfg, *env, *lp, p, g, 0, false, opt);
	if (status != SUCCESS) {
		fprintf(stdout, "***'%s': error (%d) printing the solution. . .\n", funcName, getStatusCode(status));
		freeCharArray(funcName);
		return ERR_PLOT;
	}

	//	Free memory.
	freeCharArray(funcName);
	return SUCCESS;
}

Status runBranchAndBound(const Config *cfg, Graph *g, double *UB, bool verbose) {
	char *funcName = initCharArray(cfg->NAME_LEN);
	sprintf(funcName, "runBranchAndBound");

	OneTree t, inc;
	time_t t1, t2;
	time(&t1);

	if (verbose)
		fprintf(stdout, "\t'%s': running our branch and bound algorithm, initial zOpt = %0.2f. . .\n", funcName, *UB);

	//	Initialize the memory.
	if(!initOneTree(cfg, &t, g->size)) {
		fprintf(stdout, "***'%s': memory allocation error while allocating 't'. . .\n", funcName);
		freeCharArray(funcName);
		return ERR_MEM_ALLOC;
	}
	if(!initOneTree(cfg, &inc, g->size)) {
		fprintf(stdout, "***'%s': memory allocation error while allocating 'inc'. . .\n", funcName);
		freeCharArray(funcName);
		return ERR_MEM_ALLOC;
	}

	//	Run the branch and bound algorithm.
	int decNodes = B_B_Recursive(cfg, g, &t, &inc, UB, &t1, &t2, verbose);
	if (verbose) {
		fprintf(stdout, "\t'%s': optimal TSP solution found after visiting %d decision-tree nodes. Solution cost = %0.0f. . .\n", funcName, decNodes, inc.tc);
		fprintf(stdout, "\t'%s': total time elapsed: %0.2f second(s) (%0.2f second(s) normalized time). . .\n\n", funcName, difftime(t2, t1), difftime(t2, t1) * cfg->NORM_TIME);
	}

	//	Plot the TSP solution.
	char *title = initCharArray(cfg->NAME_LEN);
	char *name = initCharArray(cfg->NAME_LEN);
	sprintf(title, "TSP optimal solution for '%s' (using our B&B algorithm). Optimal tour cost = %0.0f", g->name, inc.tc);
	sprintf(name, "%soptSolution.dat", cfg->PLT_PATH);
	plotTour(cfg, &inc, name, title, cfg->COLOR_GREEN);

	//	Free the memory.
	freeCharArray(funcName);
	disposeOneTree(&t);
	disposeOneTree(&inc);
	freeCharArray(title);
	freeCharArray(name);
	return SUCCESS;
}

Status releaseMemory(const Config *cfg, CPXENVptr *env, CPXLPptr *lp, Problem *p, Graph *g, bool lagrOpt, bool ps, CPXLPptr *psLP, Problem *psP) {
	char *funcName = initCharArray(cfg->NAME_LEN);
	sprintf(funcName, "releaseMemory");

	int cpxStat;
	bool useBB = (*lp == NULL && *env == NULL) ? true : false;

	//	Free memory for the CPLEX 'lp' problem.
	if (*lp != NULL) {
		cpxStat = CPXfreeprob(*env, lp);
		if (cpxStat != CPX_SUCCESS) {
			fprintf(stdout, "***'%s': error releasing the problem 'lp'. Status: %d. . .\n", funcName, cpxStat);
			freeCharArray(funcName);
			disposeGraph(g);
			gnuplot_close(cfg->plt);
			if (!lagrOpt)
				disposeProblem(p);
			if(ps)
				disposeProblem(psP);
			return ERR_CPX;
		}
	}

	//	Free memory for CPLEX 'psLP' problem.
	if (ps) {
		if (*psLP != NULL) {
			cpxStat = CPXfreeprob(*env, psLP);
			if (cpxStat != CPX_SUCCESS) {
				fprintf(stdout, "***'%s': error releasing the problem 'psLP'. Status: %d. . .\n", funcName, cpxStat);
				freeCharArray(funcName);
				disposeGraph(g);
				gnuplot_close(cfg->plt);
				if (!lagrOpt)
					disposeProblem(p);
				if(ps)
					disposeProblem(psP);
				return ERR_CPX;
			}
		}
	}

	//	Free memory for the CPLEX 'env' environment.
	if (*env != NULL) {
		cpxStat = CPXcloseCPLEX (env);
		if (cpxStat != CPX_SUCCESS) {
			char errmsg[CPXMESSAGEBUFSIZE];
			CPXgeterrorstring(*env, cpxStat, errmsg);
			fprintf (stdout, "***'%s': could not close CPLEX environment. Error: %s. . .\n", funcName, errmsg);
			freeCharArray(funcName);
			disposeGraph(g);
			gnuplot_close(cfg->plt);
			if (!lagrOpt)
				disposeProblem(p);
			if(ps)
				disposeProblem(psP);
			return ERR_CPX;
		}
	}

	//	Free memory.
	freeCharArray(funcName);
	disposeGraph(g);
	gnuplot_close(cfg->plt);
	if (!lagrOpt && !useBB) {
		disposeProblem(p);
		if(ps)
			disposeProblem(psP);
	}
	return SUCCESS;
}
